描述
给出两个单词&＃xff08;start和end&＃xff09;和一个字典&＃xff0c;找出所有从start到end的最短转换序列。
变换规则如下&＃xff1a;
- 每次只能改变一个字母。
- 变换过程中的中间单词必须在字典中出现。
- 所有单词具有相同的长度。
所有单词都只包含小写字母。
题目确保存在合法的路径。
在线评测地址&＃xff1a;
LintCode 领扣
样例1
输入&＃xff1a;start &＃61; "a"&＃xff0c;end &＃61; "c"&＃xff0c;dict &＃61;["a","b","c"]
输出&＃xff1a;[["a","c"]]
解释&＃xff1a;
"a"->"c"
样例2
输入&＃xff1a;start &＃61;"hit"&＃xff0c;end &＃61; "cog"&＃xff0c;dict &＃61;["hot","dot","dog","lot","log"]
输出&＃xff1a;[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释&＃xff1a;
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
从 end 到 start 做一次 BFS&＃xff0c;并且把距离 end 的距离都保存在 distance 中。 然后在从 start 到 end 做一次 DFS&＃xff0c;每走一步必须确保离 end 的 distance 越来越近。
与另外一个代码中提前建立 index 不同&＃xff0c;这里是在寻找下一个变换单词的时候&＃xff0c;再去获得对应的单词列表。一个单词最多有 L 个字符&＃xff0c;每个字符有 25 种不同的变化&＃xff08;26个字母除掉这个位置上的字母&＃xff09;&＃xff0c;然后 check 一下在不在 dict 里就知道是不是 next word 了。
from collections import deque class Solution: """
&＃64;param: start: a string
&＃64;param: end: a string
&＃64;param: dict: a set of string
&＃64;return: a list of lists of string
""" def findLadders(self, start, end, dict): dict.add(start) dict.add(end) distance &＃61; {} self.bfs(end, distance, dict) results &＃61; [] self.dfs(start, end, distance, dict, [start], results) return results def bfs(self, start, distance, dict): distance[start] &＃61; 0 queue &＃61; deque([start]) while queue: word &＃61; queue.popleft() for next_word in self.get_next_words(word, dict): if next_word not in distance: distance[next_word] &＃61; distance[word] &＃43; 1 queue.append(next_word) def get_next_words(self, word, dict): words &＃61; [] for i in range(len(word)): for c in &＃39;abcdefghijklmnopqrstuvwxyz&＃39;: next_word &＃61; word[:i] &＃43; c &＃43; word[i &＃43; 1:] if next_word !&＃61; word and next_word in dict: words.append(next_word) return words def dfs(self, curt, target, distance, dict, path, results): if curt &＃61;&＃61; target: results.append(list(path)) return for word in self.get_next_words(curt, dict): if distance[word] !&＃61; distance[curt] - 1: continue path.append(word) self.dfs(word, target, distance, dict, path, results) path.pop()
更多题解参考&＃xff1a;九章算法
京公网安备 11010802041100号